//
// Description: 1815. 得到新鲜甜甜圈的最多组数
// Created by Loading on 2021/6/12.
//

#include <bits/stdc++.h>

using namespace std;

//计算
int calc(int &cnt, int batchSize, const vector<int> &vec) {
    long long sum = 0;
    int result = 0;
    //题目要求可以理解为前缀和序列中能够整除 batchSize 的最大元素个数
    for (auto &x : vec) {
        sum += x;
        if (sum % batchSize == 0) {
            ++result;
            sum = 0;
        }
    }
    //如果有剩余，则至少一人可以获得新鲜甜甜圈
    if (sum > 0) {
        ++result;
    }
    //更新算法最优值
    cnt = max(cnt, result);
    //返回此次计算结果
    return result;
}

// https://baike.baidu.com/item/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB%E7%AE%97%E6%B3%95/355508?fr=aladdin
/* 模拟退火算法 */
/* 来源于固体退火原理，将固体温度升至最高，而后缓慢降温的过程 */
void simulated_annealing(int &cnt, int batchSize, vector<int> &vec) {
    //用 1e6 模拟最高温，1e-5 模拟最低温，0.97 为退火系数，均可调，此循环 832 次
    for (double t = 1e6; t > 1e-5; t *= 0.97) {
        //随机选取 vec 序列的两个位置
        int i = rand() % vec.size();
        int j = rand() % vec.size();
        //交换之前序列 计算结果
        int last_value = calc(cnt, batchSize, vec);
        swap(vec[i], vec[j]);
        //交换之后序列 计算结果
        int current_value = calc(cnt, batchSize, vec);
        //两次结果的差值
        /* 评价函数 */
        int delta = current_value - last_value;
        /* 若交换之后比交换之前效果要差，即 delta < 0 时，根据概率考虑保留，否则一定保留 */
        /* 且当前概率小于一个随机概率 (double) rand() / RAND_MAX，则不保留 */

        /*
         * exp(delta / t) 为当前概率，delta 小于 0，t > 0，
         * t 越小，则越趋于稳定，概率越低，越不容易保留结果；
         * delta 越大，则误差越大，概率越低，越不容易保留结果；
         */
        if (delta < 0 && exp(delta / t) < (double) rand() / RAND_MAX) {
            //结果不保留，还原交换
            swap(vec[i], vec[j]);
        }
    }
}

int maxHappyGroups(int batchSize, vector<int> &groups) {
    if (batchSize == 1) {
        return groups.size();
    }

    //返回的结果
    int res = 0;
    vector<int> vec;
    for (auto &x : groups) {
        if (x % batchSize) {
            //不能够整除的，加入 vec
            vec.emplace_back(x);
        } else {
            ++res;
        }
    }
    //vec 中数据在 2 个以下，0 个时，则没有不能整除的值；1 个时，也必然能够获得新鲜甜甜圈
    if (vec.size() < 2) {
        return res + vec.size();
    }

    //模拟退火算法最优值
    int cnt = 0;
    //调用 30 次模拟退火算法，次数可调
    for (int i = 0; i < 30; ++i) {
        simulated_annealing(cnt, batchSize, vec);
    }

    return res + cnt;
}

int main() {
    int batchSize = 4;
    vector<int> groups = {1, 3, 2, 5, 2, 2, 1, 6};

    cout << maxHappyGroups(batchSize, groups) << endl;
}